package 单向无头链表;

import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: MENG
 * Date: 2022-07-03
 * Time: 22:00
 */
public class Test {

    //输入两个链表，找出它们的第一个公共结点
    public static ListNode getIntersectionNode(ListNode head1, ListNode head2){
        ListNode pl = head1;//定义pl始终为长的链表
        ListNode ps = head2;////定义ps始终为短的链表
        int lenA = 0;//记录链表的长度
        int lenB = 0;
        while(pl != null){
            lenA++;
            pl = pl.next;
        }
        while(ps != null){
            lenB++;
            ps = ps.next;
        }
        //现在pl和ps都是null了，让他们重新指向head；
        pl = head1;
        ps = head2;

        //求插值，并让插值一直都>0
        int len = lenA - lenB;
        if(lenA - lenB < 0){
            pl = head2;//让pl总是长的链表的长度
            ps = head1;
            len = lenB - lenA;
        }
        //让长链表的指针先走len（差值）步
        while(len != 0){
            pl = pl.next;
            len--;
        }
        //两个指针一起走直到相遇
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;

        }
        return pl;


    }
    //合并两个链表的方法
    public static ListNode mergeTwoLists(ListNode head1, ListNode head2){
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(head1 != null && head2 != null){
            //合并的两个链表也要按顺序排列，所以通过比较两个链表对应位置的val值，出现两种情况。
            if(head1.val < head2.val){
                tmp.next = head1;
                head1 = head1.next;
                tmp = tmp.next;
            }else{
                tmp.next = head2;
                head2 = head2.next;
                tmp = tmp.next;
            }
            if(head1 != null){
                tmp.next = head1;
            }
            if(head2 != null){
                tmp.next = head2;
            }
        }
        return newHead.next;
    }

    public static void main2(String[] args) {
        TestSingleList test1 = new TestSingleList();
        test1.addLast(12);
        test1.addLast(13);
        test1.addLast(14);
        test1.addLast(15);

        TestSingleList test2 = new TestSingleList();
        test2.addLast(1);
        test2.addLast(2);
        test2.addLast(50);
        test2.addLast(98);
        ListNode ret = mergeTwoLists(test1.head, test2.head);
        test1.disPlay(ret);
    }
    public static void main1(String[] args) {
        TestSingleList myLinkedList = new TestSingleList();
//        myLinkedList.creatList();
//        myLinkedList.disPlay();

        myLinkedList.addFirst(12);
        myLinkedList.addFirst(12);
        myLinkedList.addLast(99);
        myLinkedList.addLast(12);
        myLinkedList.addLast(100);
        myLinkedList.disPlay();
/*        System.out.println(myLinkedList.contains(99));
        System.out.println(myLinkedList.size());
        myLinkedList.addIndex(2,56);*/
        System.out.println();

        /*//第二种方法的removeAll
        Node ret = myLinkedList.removeAll(12);
        myLinkedList.disPlay1(ret);*/
    }
}